最小表示法求字符串循环节
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s,s2;
    cin>>s;
    int len=s.length();
    s+=s;
    int flag=0;
    int i=0,j=1;
    int n=s.length()/2;
    while(i<n&&j<n)
    {
        int k=0;
        while(k<n&&s[i+k]==s[j+k]) k++;
        if(k==n)//长度为n时存在循环节
        {
            flag=1;
            break;
        }
        if(s[i+k]>s[j+k]) i+=k+1;
        else j+=k+1;
        if(i==j) j++;
    }
    if(flag==1)
    {
        int k=min(i,j);
        for(int l=0;l<abs(i-j);l++)
            cout<<s[k+l];
    }
    else
        cout<<"NO"<<endl;

}


manacher
//给定一个长度为 n 的由小写字母构成的字符串，求它的最长回文子串的长度是多少。
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e7 + 10;

int n;
char a[N], b[N];
int p[N];//p[i] 表示以 i 为中心的最长回文的半径,添加字符之后数组长度变为二倍以上

void init()
{
    int k = 0;
    b[k ++ ] = '$', b[k ++ ] = '#';
    for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
    b[k ++ ] = '^';
    n = k;
}

void manacher()
{
    int mr = 0, mid;
    for (int i = 1; i < n; i ++ )
    {
        if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
        else p[i] = 1;
        while (b[i - p[i]] == b[i + p[i]]) p[i] ++ ;
        if (i + p[i] > mr)
        {
            mr = i + p[i];
            mid = i;
        }
    }
}

int main()
{
    scanf("%s", a);
    n = strlen(a);

    init();
    manacher();

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, p[i]);
    printf("%d\n", res - 1);

    return 0;
}


后缀数组
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, m;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];//x:每个后缀的第一关键字 y：第二关键字顺序 c：每个关键字的个数

void get_sa()
{
    for (int i = 0; i < N; i++ ) c[i] = 0;//多样例时清空c数组
    //按照第一关键字排序
    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;//统计各第一关键字个数 ps.赋值运算返回左值的引用
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];//求关键字个数的前缀和
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;//倒序：保证排序稳定 每对一个关键字排序对应的c[]--,确定一个数的排名

    for (int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        //将所有后缀按第二关键字排好序
        //y存储按第二关键字排序结果 n-k+1——n的后缀没有第二关键字,0来补上
        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;//没有第二关键字的后缀一定是最小的
        for (int i = 1; i <= n; i ++ )//第i个后缀的第二关键字就是第i+k个后缀的第一关键字
            if (sa[i] > k)
                y[ ++ num] = sa[i] - k;
        
        //再按照第一关键字排序
        for (int i = 1; i <= m; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        for (int i = n; i; i -- ) sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;//按照第二关键字顺序从后往前枚举

        swap(x, y);//将x的数据存到y
        //将前2k的数据离散化,最小为1,已经将前2k个字符排好序了
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++ )
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;//相邻的两个后缀前k个字符和后k个字符相等，则离散值不变
        if (num == n) break;//此时n个后缀已经区别开了
        m = num;//不同后缀的个数
    }
}
//sa[i]表示排名第i的是第几个后缀（从后往前的第几个后缀）

//lcp(i,j):排名第i位的后缀与排名第j位的后缀的最长公共前缀 
//lcp(i,j)=min(lcp(i,k),lcp(k,j)) i<=k<=j
//lcp(i,j)=min(lcp(i,i+1),lcp(i+1,i+2),lcp(i+2,i+3)...lcp(j-1,j))
//height[i]=lcp(i-1,i)
//lcp(i,i)=len(sa[i])=n-sa[i]+1 

//h[i]=height[rk[i]],h[i]为第i个后缀和排在第i个后缀前面的后缀之间最长公共前缀
//h[i]>=h[i-1]-1
void get_height()
{
    for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; i ++ )
    {
        if (rk[i] == 1) continue;//特别的，规定 Height[1]=0。
        if (k) k -- ;//从第k-1位枚举,因为h[i]>=h[i-1]-1
        int j = sa[rk[i] - 1];
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
        height[rk[i]] = k;
    }
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1), m = 122;//字符的最大ascii码为'z'122(大小写英文和数字中)
    get_sa();
    get_height();

    for (int i = 1; i <= n; i ++ ) printf("%d ", sa[i]);
    puts("");
    for (int i = 1; i <= n; i ++ ) printf("%d ", height[i]);
    puts("");
    return 0;
}

讲义
一、SAM的性质:

SAM是个状态机。一个起点，若干终点。原串的所有子串和从SAM起点开始的所有路径一一对应，不重不漏。所以终点就是包含后缀的点。
每个点包含若干子串，每个子串都一一对应一条从起点到该点的路径。且这些子串一定是里面最长子串的连续后缀。
SAM问题中经常考虑两种边：
(1) 普通边，类似于Trie。表示在某个状态所表示的所有子串的后面添加一个字符。
(2) Link、Father。表示将某个状态所表示的最短子串的首字母删除，然后该状态连一条指向删除首字母状态的边。这类边构成一棵树。
二、SAM的构造思路

endpos(s)：子串s所有出现的位置（尾字母下标）集合。SAM中的每个状态都一一对应一个endpos的等价类。
endpos的性质：
(1) 令 s1,s2 为 S 的两个子串 ，不妨设 |s1|≤|s2| （我们用 |s| 表示 s 的长度 ，此处等价于 s1 不长于 s2 ）。
则 s1 是 s2 的后缀当且仅当 endpos(s1)⊇endpos(s2) ，s1 不是 s2 的后缀当且仅当 endpos(s1)∩endpos(s2)=∅　。
(2) 两个不同子串的endpos，要么有包含关系，要么没有交集。
(3) 两个子串的endpos相同，那么短串为长串的后缀。
(4) 对于一个状态 st ，以及任意的 longest(st) 的后缀 s ，如果 s 的长度满足：|shortest(st)|≤|s|≤|longsest(st)| ，那么 s∈substrings(st) 。
三、SAM的构造过程
分类讨论，具体看板书。
证明较为复杂，略。

四、SAM时间复杂度
线性。
证明较为复杂，略。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 2000010;

int tot = 1, last = 1;
struct Node
{
    int len, fa;
    int ch[26];
}node[N];
char str[N];
LL f[N], ans;
int h[N], e[N], ne[N], idx;

void extend(int c)
{
    int p = last, np = last = ++ tot;
    f[tot] = 1;
    node[np].len = node[p].len + 1;
    for (; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if (!p) node[np].fa = 1;
    else
    {
        int q = node[p].ch[c];
        if (node[q].len == node[p].len + 1) node[np].fa = q;
        else
        {
            int nq = ++ tot;
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[q].fa = node[np].fa = nq;
            for (; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq;
        }
    }
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        dfs(e[i]);
        f[u] += f[e[i]];
    }
    if (f[u] > 1) ans = max(ans, f[u] * node[u].len);
}

int main()
{
    scanf("%s", str);
    for (int i = 0; str[i]; i ++ ) extend(str[i] - 'a');
    memset(h, -1, sizeof h);
    for (int i = 2; i <= tot; i ++ ) add(node[i].fa, i);
    dfs(1);
    printf("%lld\n", ans);

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/585844/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。